'''
https://leetcode.cn/problems/partition-list/description/
'''
from typing import Optional

from utils import *


class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        if head is None:return head
        big_head = big_tail = small_head = small_tail = None
        cur = head
        while cur:
            if cur.val >= x:
                if big_tail:
                    big_tail.next = cur
                    big_tail = big_tail.next
                else:
                    big_head = cur
                    big_tail = cur
            else:
                if small_tail:
                    small_tail.next = cur
                    small_tail = small_tail.next
                else:
                    small_head = cur
                    small_tail = cur
            next = cur.next
            cur.next = None
            cur = next
        if not small_tail: return big_head
        small_tail.next = big_head
        return small_head
